package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：下午1:57:41
*/
public class Q17 {
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
        if (nums == null || nums.length <= 0) {
            return rs;
        }
        Arrays.sort(nums);
        int length = nums.length;
        long n = (long) Math.pow(2, length);
        for (long i = 0; i < n; i++) {
            long k = i;
            ArrayList<Integer> result = new ArrayList<>();
            for (int j = 0; j < length; j++) {
                if ((k & 1) == 1) {
                    result.add(nums[j]);
                }
                k = (k >> 1);
            }
            rs.add(result);
        }
        return rs;
    }

    @Test
    public void testA() {
        int nums[] = { 1, 2, 3 };
        System.out.println(subsets(nums));
    }
}
